// -*- mode: ObjC -*-

//  This file is part of class-dump, a utility for examining the Objective-C segment of Mach-O files.
//  Copyright (C) 1997-2019 Steve Nygard.

#import "CDStructureTable.h"

#import "CDClassDump.h"
#import "CDType.h"
#import "CDTypeController.h"
#import "CDTypeFormatter.h"
#import "CDTypeName.h"
#import "CDStructureInfo.h"

// Phase 0 - This is driven by CDClassDump, registering types from all of the classes, categories, and protocols.
//         - This collects all the top level types (or struct/unions?), keeps a reference count, and flags any that were used in a method.
//         - If a top level struct was used in a method, then the type MUST be declared at the top.
//         - At the end of phase 0, these types are recursively visited, renaming structs whose name starts with $ (like $_12345) to ?, so
//           that we'll treat them as anonymous structures.
//            - Those names must be generated by the compiler.  It can end up with different numbers for the same type.

// Phase 1 - This goes through all the types collected in phase 0, and recursively registers each structure and union with the type controller.
//         - We are not concerned about reference counts or the isUsedInMethod flags.
//         - Since structures and unions can be nested in each other, we need to process each table before doing the end-of-phase work.
//         - We record the maximum structure depth.
//           - Since the deepest union may be buriend in a structure instead of referenced at the top level, we can't calculate the max depth from phase 0.
//           - On the other hand, since we're only interested in the max combined depth of structures and unions, the end result would be the same.
//         - The result of phase 1 is phase1_groupedByDepth: a dictionary keyed by the structure depth, containing arrays of CDStructureInfo.

// Phase 2 - This is driven by CDTypeController.
//         - The goal of phase 2 is to gather member names and types (@"NSObject" vs just @).
//         - It goes through all of the phase1 groups, shallowest to deepest.
//         - For each level group:
//           - First it merges the results of all previous groups with the types at this depth.
//           - Then we group the CDStructureInfos, named structures by name, anon structures by reallyBareTypeString
//             - If they could be combined, the combined CDStructureInfo is to phase2_namedStructureInfo or phase2_anonStructureInfo.
//             - If they couldn't be combined, the uncombined CDStructureInfos are added to phase2_nameExceptions or phase2_anonExceptions.

// Phase 3 - Using all of the information available from the merged types from phase 2, we merge these types with the types from phase 0
//           to fill in missing member names, and the occasional object type.

// After all the phases are done, typedef names are generated for all anonymous structures, and then field names are added for missing fields.
//  - bitfields don't need to have a name, so they can be blank.
//  - the typedef name is calculated from a hash of the typeString.
//    - Doing it before adding missing fields means we could change the field names without changing the typedef name.
//    - Makes the name independant of the order they were encountered (like the previous indexes were).  You can get meaningful diffs between
//      framework changes now.

static BOOL debug = NO;
static BOOL debugNamedStructures = NO;
static BOOL debugAnonStructures = NO;

@interface CDStructureTable ()
@end

#pragma mark -

@implementation CDStructureTable
{
    __weak CDTypeController *_typeController;
    
    NSString *_identifier;
    NSString *_anonymousBaseName;
    
    // Phase 0 - top level
    NSMutableDictionary *_phase0_structureInfo; // key: NSString (typeString), value: CDStructureInfo
    
    // Phase 1 - all substructures
    NSMutableDictionary *_phase1_structureInfo; // key: NSString (typeString), value: CDStructureInfo
    NSUInteger _phase1_maxDepth;
    NSMutableDictionary *_phase1_groupedByDepth; // key: NSNumber (structureDepth), value: NSMutableArray of CDStructureInfo
    
    // Phase 2 - merging all structure bottom up
    NSMutableDictionary *_phase2_namedStructureInfo; // key: NSString (name), value: CDStructureInfo
    NSMutableDictionary *_phase2_anonStructureInfo; // key: NSString (reallyBareTypeString), value: CDStructureInfo
    NSMutableArray *_phase2_nameExceptions; // Of CDStructureInfo
    NSMutableArray *_phase2_anonExceptions; // Of CDStructureInfo
    
    // Phase 3 - merged reference counts from updated phase0 types
    NSMutableDictionary *_phase3_namedStructureInfo; // key: NSString (name), value: CDStructureInfo
    NSMutableDictionary *_phase3_anonStructureInfo; // key: NSString (reallyBareTypeString), value: CDStructureInfo
    
    NSMutableDictionary *_phase3_nameExceptions; // key: NSString (typeString), value: CDStructureInfo
    NSMutableDictionary *_phase3_anonExceptions; // key: NSString (typeString), value: CDStructureInfo
    
    NSMutableSet *_phase3_exceptionalNames; // Of NSString
    NSMutableSet *_phase3_inMethodNameExceptions; // Of NSString
    
    BOOL _shouldDebug;
    
    NSMutableSet *_debugNames; // NSString (name)
    NSMutableSet *_debugAnon; // NSString (reallyBareTypeString)
}

- (id)init;
{
    if ((self = [super init])) {
        _identifier = nil;
        _anonymousBaseName = nil;
        
        _phase0_structureInfo = [[NSMutableDictionary alloc] init];
        
        _phase1_structureInfo = [[NSMutableDictionary alloc] init];
        _phase1_maxDepth = 0;
        _phase1_groupedByDepth = [[NSMutableDictionary alloc] init];
        
        _phase2_namedStructureInfo = [[NSMutableDictionary alloc] init];
        _phase2_anonStructureInfo = [[NSMutableDictionary alloc] init];
        _phase2_nameExceptions = [[NSMutableArray alloc] init];
        _phase2_anonExceptions = [[NSMutableArray alloc] init];
        
        _phase3_namedStructureInfo = [[NSMutableDictionary alloc] init];
        _phase3_anonStructureInfo = [[NSMutableDictionary alloc] init];
        _phase3_nameExceptions = [[NSMutableDictionary alloc] init];
        _phase3_anonExceptions = [[NSMutableDictionary alloc] init];
        
        _phase3_exceptionalNames = [[NSMutableSet alloc] init];
        _phase3_inMethodNameExceptions = [[NSMutableSet alloc] init];
        
        _shouldDebug = NO;
        
        _debugNames = [[NSMutableSet alloc] init];
        _debugAnon = [[NSMutableSet alloc] init];
    }

    return self;
}

#pragma mark - Phase 0

- (void)phase0RegisterStructure:(CDType *)structure usedInMethod:(BOOL)isUsedInMethod;
{
    NSString *key = structure.typeString;
    CDStructureInfo *info = _phase0_structureInfo[key];
    if (info == nil) {
        info = [[CDStructureInfo alloc] initWithType:structure];
        if (isUsedInMethod)
            info.isUsedInMethod = YES;
        _phase0_structureInfo[key] = info;
    } else {
        [info addReferenceCount:1];
        if (isUsedInMethod)
            info.isUsedInMethod = YES;
    }
}

- (void)finishPhase0;
{
    if (debug) NSLog(@"[%@] %s, changing struct names that start with $", self.identifier, __cmd);
    for (CDStructureInfo *info in [_phase0_structureInfo allValues]) {
        [info.type phase0RecursivelyFixStructureNames:debug];
    }

    if ([_debugNames count] > 0) {
        NSLog(@"======================================================================");
        NSLog(@"[%@] %s", self.identifier, __cmd);
        NSLog(@"debug names: %@", [[_debugNames allObjects] componentsJoinedByString:@", "]);
        for (CDStructureInfo *info in [[_phase0_structureInfo allValues] sortedArrayUsingSelector:@selector(ascendingCompareByStructureDepth:)]) {
            if ([_debugNames containsObject:[info.type.typeName description]])
                NSLog(@"%@", [info shortDescription]);
        }
        NSLog(@"======================================================================");
    }

    if ([_debugAnon count] > 0) {
        NSLog(@"======================================================================");
        NSLog(@"[%@] %s", self.identifier, __cmd);
        NSLog(@"debug anon: %@", [[_debugAnon allObjects] componentsJoinedByString:@", "]);
        for (CDStructureInfo *info in [[_phase0_structureInfo allValues] sortedArrayUsingSelector:@selector(ascendingCompareByStructureDepth:)]) {
            if ([_debugAnon containsObject:info.type.reallyBareTypeString])
                NSLog(@"%@", [info shortDescription]);
        }
        NSLog(@"======================================================================");
    }
}

#pragma mark - Phase 1

- (void)runPhase1;
{
    for (CDStructureInfo *info in [_phase0_structureInfo allValues]) {
        [info.type phase1RegisterStructuresWithObject:self.typeController];
    }
}

// Need to gather all of the structures, since some substructures may have member names we'd otherwise miss.
- (void)phase1RegisterStructure:(CDType *)structure;
{
    NSString *key = structure.typeString;
    CDStructureInfo *info = _phase1_structureInfo[key];
    if (info == nil) {
        info = [[CDStructureInfo alloc] initWithType:structure];
        _phase1_structureInfo[key] = info;
    }
}

// Need to merge names bottom-up to catch cases like: {?=@@iiffff{_NSRect={_NSPoint=ff}{_NSSize=ff}}{?=b1b1b1b1b1b27}}

- (void)finishPhase1;
{
    if (debug) {
        NSLog(@"======================================================================");
        NSLog(@"[%@] %s", self.identifier, __cmd);
    }

    // The deepest union may not be at the top level (buried in a structure instead), so need to get the depth here.
    // But we'll take the max of structure and union depths in the CDTypeController anyway.

    for (CDStructureInfo *info in [_phase1_structureInfo allValues]) {
        NSUInteger depth = info.type.structureDepth;
        if (_phase1_maxDepth < depth)
            _phase1_maxDepth = depth;
    }
    if (debug) NSLog(@"[%@] Maximum structure depth is: %lu", self.identifier, _phase1_maxDepth);

    for (CDStructureInfo *info in [_phase1_structureInfo allValues]) {
        NSNumber *key = [NSNumber numberWithUnsignedInteger:info.type.structureDepth];
        NSMutableArray *group = _phase1_groupedByDepth[key];
        if (group == nil) {
            group = [[NSMutableArray alloc] init];
            [group addObject:info];
            _phase1_groupedByDepth[key] = group;
        } else {
            [group addObject:info];
        }
    }

    if (debug) NSLog(@"depth groups: %@", [[_phase1_groupedByDepth allKeys] sortedArrayUsingSelector:@selector(compare:)]);
}

- (NSUInteger)phase1_maxDepth;
{
    return _phase1_maxDepth;
}

#pragma mark - Phase 2

// From lowest to highest depths:
// - Go through all infos at that level
//   - recursively (bottom up) try to merge substructures into that type, to get names/full types
// - merge all mergeable infos at that level

- (void)runPhase2AtDepth:(NSUInteger)depth;
{
    //NSLog(@"[%@] %s, depth: %u", identifier, __cmd, depth);
    NSNumber *depthKey = [NSNumber numberWithUnsignedInteger:depth];
    NSArray *infos = _phase1_groupedByDepth[depthKey];

    for (CDStructureInfo *info in infos) {
        // recursively (bottom up) try to merge substructures into that type, to get names/full types
        //NSLog(@"----------------------------------------");
        //NSLog(@"Trying phase2Merge with on %@", [[info type] typeString]);
        [info.type phase2MergeWithTypeController:self.typeController debug:debug];
    }

    // merge all mergeable infos at that level
    NSMutableDictionary *nameDict = [NSMutableDictionary dictionary];
    NSMutableDictionary *anonDict = [NSMutableDictionary dictionary];

    // Group named structures by name.
    // Group anon structures by reallyBareTypeString.
    for (CDStructureInfo *info in infos) {
        NSString *name = [info.type.typeName description];

        if ([@"?" isEqualToString:name]) {
            NSString *key = info.type.reallyBareTypeString;
            NSMutableArray *group = anonDict[key];
            if (group == nil) {
                group = [[NSMutableArray alloc] init];
                [group addObject:info];
                anonDict[key] = group;
            } else {
                [group addObject:info];
            }
        } else {
            NSMutableArray *group = nameDict[name];
            if (group == nil) {
                group = [[NSMutableArray alloc] init];
                [group addObject:info];
                nameDict[name] = group;
            } else {
                [group addObject:info];
            }
        }
    }

    // Now... for each group, make sure we can combine them all together.
    // If not, this means that either the types or the member names conflicted, and we save the entire group as an exception.
    for (NSString *key in [nameDict allKeys]) {
        CDStructureInfo *combined = nil;

        //NSLog(@"key... %@", key);
        NSMutableArray *group = nameDict[key];
        for (CDStructureInfo *info in group) {
            if (combined == nil) {
                combined = [info copy];
            } else {
                //NSLog(@"old: %@", [[combined type] typeString]);
                //NSLog(@"new: %@", [[info type] typeString]);
                if ([combined.type canMergeWithType:info.type]) {
                    [combined.type mergeWithType:info.type];
                    [combined addReferenceCount:info.referenceCount];
#if 0
                    if (info.isUsedInMethod)
                        combined.isUsedInMethod = YES;
#endif
                } else {
                    combined = nil;
                    break;
                }
            }
        }

        if (combined != nil) {
            CDStructureInfo *previousInfo = _phase2_namedStructureInfo[key];
            if (previousInfo != nil) {
                // struct _Vector_impl in HALLab.
                [_phase2_nameExceptions addObject:previousInfo];
                //[phase2_nameExceptions addObjectsFromArray:group]; // Or just add the combined?
                [_phase2_nameExceptions addObject:combined];
                [_phase2_namedStructureInfo removeObjectForKey:key];
                if (debugNamedStructures) {
                    NSLog(@"[%@] %s, WARNING: depth %lu name %@ has conflict(?) at lower level", self.identifier, __cmd, depth, key);
                    NSLog(@"previous: %@", [_phase2_namedStructureInfo[key] shortDescription]);
                    NSLog(@" current: %@", [combined shortDescription]);
                }
            } else {
                _phase2_namedStructureInfo[key] = combined;
            }
        } else {
            if (debugNamedStructures) {
                NSLog(@"----------------------------------------");
                NSLog(@"Can't be combined: %@", key);
                NSLog(@"group: %@", group);
            }
            [_phase2_nameExceptions addObjectsFromArray:group];
        }
    }

    //NSLog(@"======================================================================");
    for (NSString *key in [anonDict allKeys]) {
        CDStructureInfo *combined = nil;

        //NSLog(@"key... %@", key);
        NSMutableArray *group = anonDict[key];
        for (CDStructureInfo *info in group) {
            if (combined == nil) {
                combined = [info copy];
                //NSLog(@"info: %@", [info shortDescription]);
                //NSLog(@"combined: %@", [combined shortDescription]);
            } else {
                //NSLog(@"old: %@", [combined shortDescription]);
                //NSLog(@"new: %@", [info shortDescription]);
                if ([combined.type canMergeWithType:info.type]) {
                    [combined.type mergeWithType:info.type];
                    [combined addReferenceCount:info.referenceCount];
#if 0
                    if (info.isUsedInMethod)
                        combined.isUsedInMethod = YES;
#endif
                } else {
                    if (debugAnonStructures) {
                        NSLog(@"previous: %@", combined.type.typeString);
                        NSLog(@"    This: %@", info.type.typeString);
                    }
                    combined = nil;
                    break;
                }
            }
        }

        if (combined != nil) {
            if (_phase2_anonStructureInfo[key] != nil) {
                // This shouldn't happen, but the named case might.
                NSLog(@"[%@] %s, WARNING: depth %lu type %@ has conflict(?) at lower level", self.identifier, __cmd, depth, key);
                NSLog(@"previous: %@", [_phase2_anonStructureInfo[key] shortDescription]);
                NSLog(@" current: %@", [combined shortDescription]);
            }
            _phase2_anonStructureInfo[key] = combined;
        } else {
            if (debugAnonStructures) {
                NSLog(@"----------------------------------------");
                NSLog(@"Can't be combined: %@", key);
                NSLog(@"group: %@", group);
            }
            [_phase2_anonExceptions addObjectsFromArray:group];
        }
    }
}

- (CDType *)phase2ReplacementForType:(CDType *)type;
{
    NSString *name = [type.typeName description];
    CDStructureInfo *info;

    if ([@"?" isEqualToString:name]) {
        info = _phase2_anonStructureInfo[type.reallyBareTypeString];
    } else {
        info = _phase2_namedStructureInfo[name];
    }

    return info.type;
}

- (void)finishPhase2;
{
    if ([_debugNames count] > 0) {
        NSLog(@"======================================================================");
        NSLog(@"[%@] %s", self.identifier, __cmd);
        NSLog(@"debug names: %@", [[_debugNames allObjects] componentsJoinedByString:@", "]);
        for (CDStructureInfo *info in [[_phase2_namedStructureInfo allValues] sortedArrayUsingSelector:@selector(ascendingCompareByStructureDepth:)]) {
            if ([_debugNames containsObject:[info.type.typeName description]])
                NSLog(@"%@", [info shortDescription]);
        }
        NSLog(@"======================================================================");
    }

    if ([_debugAnon count] > 0) {
        NSLog(@"======================================================================");
        NSLog(@"[%@] %s", self.identifier, __cmd);
        NSLog(@"debug anon: %@", [[_debugAnon allObjects] componentsJoinedByString:@", "]);
        for (CDStructureInfo *info in [[_phase2_anonStructureInfo allValues] sortedArrayUsingSelector:@selector(ascendingCompareByStructureDepth:)]) {
            if ([_debugAnon containsObject:info.type.reallyBareTypeString])
                NSLog(@"%@", [info shortDescription]);
        }
        NSLog(@"======================================================================");
    }

    //[self logPhase2Info];
}

#pragma mark - Phase 3

- (void)phase2ReplacementOnPhase0;
{
    if (debug) {
        NSLog(@"======================================================================");
        NSLog(@"[%@]  > %s", self.identifier, __cmd);
    }

    for (CDStructureInfo *info in [_phase0_structureInfo allValues]) {
        [info.type phase2MergeWithTypeController:self.typeController debug:debug];
    }

    if (debug) NSLog(@"[%@] <  %s", self.identifier, __cmd);
}

// Go through all updated phase0_structureInfo types
// - start merging these into a new table
//   - If this is the first time a structure has been added:
//     - add one reference for each subtype
//   - otherwise just merge them.
// - end result should be CDStructureInfos with counts and method reference flags

- (void)buildPhase3Exceptions;
{
    for (CDStructureInfo *info in _phase2_nameExceptions) {
        CDStructureInfo *newInfo = [info copy];
        newInfo.referenceCount = 0;
        newInfo.isUsedInMethod = NO;
        _phase3_nameExceptions[newInfo.type.typeString] = newInfo;
        [_phase3_exceptionalNames addObject:newInfo.name];
    }

    for (CDStructureInfo *info in _phase2_anonExceptions) {
        CDStructureInfo *newInfo = [info copy];
        newInfo.referenceCount = 0;
        newInfo.isUsedInMethod = NO;
        _phase3_anonExceptions[newInfo.type.typeString] = newInfo;
    }

    //NSLog(@"phase3 name exceptions: %@", [[phase3_nameExceptions allKeys] componentsJoinedByString:@", "]);
    //NSLog(@"phase3 anon exceptions: %@", [[phase3_anonExceptions allKeys] componentsJoinedByString:@"\n"]);
    //exit(99);
}

- (void)runPhase3;
{
    //NSLog(@"[%@]  > %s", identifier, __cmd);

    for (CDStructureInfo *info in [[_phase0_structureInfo allValues] sortedArrayUsingSelector:@selector(ascendingCompareByStructureDepth:)]) {
        [self phase3RegisterStructure:info.type count:info.referenceCount usedInMethod:info.isUsedInMethod];
    }

    //NSLog(@"[%@] <  %s", identifier, __cmd);
}

- (void)phase3RegisterStructure:(CDType *)structure
                          count:(NSUInteger)referenceCount
                   usedInMethod:(BOOL)isUsedInMethod
{
    //NSLog(@"[%@]  > %s", identifier, __cmd);

    NSString *name = [structure.typeName description];
    if ([@"?" isEqualToString:name]) {
        NSString *key = structure.reallyBareTypeString;
        //NSLog(@"key: %@, isUsedInMethod: %u", key, isUsedInMethod);
        CDStructureInfo *info = _phase3_anonExceptions[structure.typeString];
        if (info != nil) {
            if (debugAnonStructures) NSLog(@"%s, anon key %@ has exception from phase 2", __cmd, structure.typeString);
            [info addReferenceCount:referenceCount];
            if (isUsedInMethod)
                info.isUsedInMethod = YES;

            if (info.referenceCount == referenceCount) { // i.e. the first time we've encounter this struct
                // And then... add 1 reference for each substructure, stopping recursion when we've encountered a previous structure
                [structure phase3RegisterMembersWithTypeController:self.typeController];
            }
        } else {
            info = _phase3_anonStructureInfo[key];
            if (info == nil) {
                info = [[CDStructureInfo alloc] initWithType:structure];
                [info setReferenceCount:referenceCount];
                if (isUsedInMethod)
                    info.isUsedInMethod = YES;
                _phase3_anonStructureInfo[key] = info;

                // And then... add 1 reference for each substructure, stopping recursion when we've encountered a previous structure
                [structure phase3RegisterMembersWithTypeController:self.typeController];
            } else {
                [info addReferenceCount:referenceCount];
                if (isUsedInMethod)
                    info.isUsedInMethod = YES;
            }
        }
    } else {
        if ([_debugNames containsObject:name]) NSLog(@"[%@] %s, type= %@", self.identifier, __cmd, structure.typeString);
        //NSLog(@"[%@] %s, name: %@", identifier, __cmd, name);
        if ([_phase3_exceptionalNames containsObject:name]) {
            if (debugNamedStructures) NSLog(@"%s, name %@ has exception from phase 2", __cmd, name);
            CDStructureInfo *info = _phase3_nameExceptions[structure.typeString];
            // Info can be nil.  For example, from {_CommandStackEntry}
            if (info != nil) {
                [info addReferenceCount:referenceCount];
                if (isUsedInMethod)
                    [_phase3_inMethodNameExceptions addObject:name];

                if (info.referenceCount == referenceCount) { // i.e. the first time we've encounter this struct
                    // And then... add 1 reference for each substructure, stopping recursion when we've encountered a previous structure
                    [structure phase3RegisterMembersWithTypeController:self.typeController];
                }
            }
        } else {
            CDStructureInfo *info = _phase3_namedStructureInfo[name];
            if (info == nil) {
                if ([_debugNames containsObject:name]) NSLog(@"[%@] %s, info was nil for %@", self.identifier, __cmd, name);
                info = [[CDStructureInfo alloc] initWithType:structure];
                [info setReferenceCount:referenceCount];
                if (isUsedInMethod)
                    info.isUsedInMethod = YES;
                _phase3_namedStructureInfo[name] = info;

                // And then... add 1 reference for each substructure, stopping recursion when we've encountered a previous structure
                [structure phase3RegisterMembersWithTypeController:self.typeController];
            } else {
                if ([_debugNames containsObject:name]) NSLog(@"[%@] %s, info before: %@", self.identifier, __cmd, [info shortDescription]);
                // Handle the case where {foo} occurs before {foo=iii}
                if ([info.type.members count] == 0) {
                    [info.type mergeWithType:structure];

                    // And then... add 1 reference for each substructure, stopping recursion when we've encountered a previous structure
                    [structure phase3RegisterMembersWithTypeController:self.typeController];
                }
                [info addReferenceCount:referenceCount];
                if (isUsedInMethod)
                    info.isUsedInMethod = YES;
                if ([_debugNames containsObject:name]) {
                    NSLog(@"[%@] %s, added ref count: %lu, isUsedInMethod: %u", self.identifier, __cmd, referenceCount, isUsedInMethod);
                    NSLog(@"[%@] %s, info after: %@", self.identifier, __cmd, [info shortDescription]);
                }
            }
        }
    }

    //NSLog(@"[%@] <  %s", identifier, __cmd);
}

- (void)finishPhase3;
{
    if ([_debugNames count] > 0) {
        NSLog(@"======================================================================");
        NSLog(@"[%@] %s", self.identifier, __cmd);
        NSLog(@"names: %@", [[_debugNames allObjects] componentsJoinedByString:@", "]);
        for (CDStructureInfo *info in [[_phase3_namedStructureInfo allValues] sortedArrayUsingSelector:@selector(ascendingCompareByStructureDepth:)]) {
            if ([_debugNames containsObject:[info.type.typeName description]])
                NSLog(@"%@", [info shortDescription]);
        }
        for (CDStructureInfo *info in [_phase3_nameExceptions allValues]) {
            if ([_debugNames containsObject:[info name]])
                NSLog(@"%@ is in the name exceptions", info.name);
        }
        NSLog(@"======================================================================");
    }

    if ([_debugAnon count] > 0) {
        NSLog(@"======================================================================");
        NSLog(@"[%@] %s", self.identifier, __cmd);
        NSLog(@"debug anon: %@", [[_debugAnon allObjects] componentsJoinedByString:@", "]);
        for (CDStructureInfo *info in [[_phase3_anonStructureInfo allValues] sortedArrayUsingSelector:@selector(ascendingCompareByStructureDepth:)]) {
            if ([_debugAnon containsObject:info.type.reallyBareTypeString])
                NSLog(@"%@", [info shortDescription]);
        }
        for (NSString *str in _debugAnon)
            if (_phase3_anonExceptions[str] != nil)
                NSLog(@"%@ is in the anon exceptions", str);
        NSLog(@"======================================================================");
    }

    //[self logPhase3Info];
}

- (CDType *)phase3ReplacementForType:(CDType *)type;
{
    NSString *name = [type.typeName description];
    CDStructureInfo *info;
    
    if ([@"?" isEqualToString:name]) {
        info = _phase3_anonStructureInfo[type.reallyBareTypeString];
    } else {
        info = _phase3_namedStructureInfo[name];
    }

    return info.type;
}

#pragma mark - Other

- (void)generateTypedefNames;
{
    for (CDStructureInfo *info in [_phase3_anonStructureInfo allValues]) {
        [info generateTypedefName:self.anonymousBaseName];
    }
    
    // And do the same for each of the anon exceptions
    for (CDStructureInfo *info in [_phase3_anonExceptions allValues]) {
        [info generateTypedefName:self.anonymousBaseName];
    }
    
    for (CDStructureInfo *info in [_phase3_nameExceptions allValues]) {
        [info generateTypedefName:[NSString stringWithFormat:@"%@_", info.type.typeName.name]];
        info.type.typeName.name = @"?";
    }
    
    for (CDStructureInfo *info in [_phase3_namedStructureInfo allValues]) {
        if (info.type.isTemplateType && info.isUsedInMethod) {
            [info generateTypedefName:[NSString stringWithFormat:@"%@_", info.type.typeName.name]];
        }
    }
}

- (void)generateMemberNames;
{
    for (CDStructureInfo *info in [_phase3_namedStructureInfo allValues]) {
        [info.type generateMemberNames];
    }
    
    for (CDStructureInfo *info in [_phase3_anonStructureInfo allValues]) {
        [info.type generateMemberNames];
    }
    
    for (CDStructureInfo *info in [_phase3_nameExceptions allValues]) {
        [info.type generateMemberNames];
    }
    
    // And do the same for each of the anon exceptions
    for (CDStructureInfo *info in [_phase3_anonExceptions allValues]) {
        [info.type generateMemberNames];
    }
}

// TODO: (2003-12-23) Add option to show/hide this section
// TODO: (2003-12-23) sort by name or by dependency
// TODO: (2003-12-23) declare in modules where they were first used

- (void)appendNamedStructuresToString:(NSMutableString *)resultString
                            formatter:(CDTypeFormatter *)typeFormatter
                             markName:(NSString *)markName;
{
    BOOL hasAddedMark = NO;
    BOOL hasShownExceptions = NO;

    for (NSString *key in [[_phase3_namedStructureInfo allKeys] sortedArrayUsingSelector:@selector(compare:)]) {
        CDStructureInfo *info = _phase3_namedStructureInfo[key];
        BOOL shouldShow = ![self shouldExpandStructureInfo:info];
        if (shouldShow || debugNamedStructures) {
            if (hasAddedMark == NO) {
                [resultString appendFormat:@"#pragma mark %@\n\n", markName];
                hasAddedMark = YES;
            }

            CDType *type = info.type;
            if ([typeFormatter.typeController shouldShowName:[type.typeName description]]) {
                if (debugNamedStructures) {
                    [resultString appendFormat:@"// would normally show? %u\n", shouldShow];
                    [resultString appendFormat:@"// depth: %lu, ref count: %lu, used in method? %u\n", info.type.structureDepth, info.referenceCount, info.isUsedInMethod];
                }
                NSString *formattedString = [typeFormatter formatVariable:nil type:type];
                if (formattedString != nil) {
                    [resultString appendString:formattedString];
                    [resultString appendString:@";\n\n"];
                }
            }
        }
    }

    for (CDStructureInfo *info in [[_phase3_nameExceptions allValues] sortedArrayUsingSelector:@selector(ascendingCompareByStructureDepth:)]) {
        BOOL shouldShow = ![self shouldExpandStructureInfo:info];
        if (shouldShow || debugNamedStructures) {
            if (hasAddedMark == NO) {
                [resultString appendFormat:@"#pragma mark %@\n\n", markName];
                hasAddedMark = YES;
            }

            if (hasShownExceptions == NO) {
                [resultString appendString:@"#if 0\n"];
                [resultString appendString:@"// Names with conflicting types:\n"];
                hasShownExceptions = YES;
            }

            CDType *type = info.type;
            if ([typeFormatter.typeController shouldShowName:[type.typeName description]]) {
                if (debugNamedStructures) {
                    [resultString appendFormat:@"// depth: %lu, ref count: %lu, used in method? %u\n", info.type.structureDepth, info.referenceCount, info.isUsedInMethod];
                    //[resultString appendFormat:@"// typedefName: %@\n", [info typedefName]];
                }
                NSString *formattedString = [typeFormatter formatVariable:nil type:type];
                if (formattedString != nil) {
                    [resultString appendFormat:@"typedef %@ %@;\n\n", formattedString, info.typedefName];
                }
            }
        }
    }
    if (hasShownExceptions)
        [resultString appendString:@"#endif\n\n"];

    if (debugNamedStructures) {
        [resultString appendString:@"\n// Name exceptions:\n"];
        for (CDStructureInfo *info in [[_phase3_nameExceptions allValues] sortedArrayUsingSelector:@selector(ascendingCompareByStructureDepth:)])
            [resultString appendFormat:@"// %@\n", [info shortDescription]];
        [resultString appendString:@"\n"];
    }
}

- (void)appendTypedefsToString:(NSMutableString *)resultString
                     formatter:(CDTypeFormatter *)typeFormatter
                      markName:(NSString *)markName;
{
    BOOL hasAddedMark = NO;
    BOOL hasShownExceptions = NO;

    for (CDStructureInfo *info in [[_phase3_anonStructureInfo allValues] sortedArrayUsingSelector:@selector(ascendingCompareByStructureDepth:)]) {
        BOOL shouldShow = ![self shouldExpandStructureInfo:info];
        if (shouldShow || debugAnonStructures) {
            if (hasAddedMark == NO) {
                [resultString appendFormat:@"#pragma mark %@\n\n", markName];
                hasAddedMark = YES;
            }

            if (debugAnonStructures) {
                [resultString appendFormat:@"// would normally show? %u\n", shouldShow];
                [resultString appendFormat:@"// %@\n", info.type.reallyBareTypeString];
                [resultString appendFormat:@"// depth: %lu, ref: %lu, used in method? %u\n", info.type.structureDepth, info.referenceCount, info.isUsedInMethod];
            }

            NSString *formattedString = [typeFormatter formatVariable:nil type:info.type];
            if (formattedString != nil) {
                [resultString appendFormat:@"typedef %@ %@;\n\n", formattedString, info.typedefName];
            }
        }
    }

    // TODO: (2009-08-25) Need same ref count rules for anon exceptions.
    for (CDStructureInfo *info in [[_phase3_anonExceptions allValues] sortedArrayUsingSelector:@selector(ascendingCompareByStructureDepth:)]) {
        BOOL shouldShow = ![self shouldExpandStructureInfo:info];
        if (shouldShow || debugAnonStructures) {
            if (hasAddedMark == NO) {
                [resultString appendFormat:@"#pragma mark %@\n\n", markName];
                hasAddedMark = YES;
            }

            if (hasShownExceptions == NO) {
                [resultString appendString:@"// Ambiguous groups\n"];
                hasShownExceptions = YES;
            }

            if (debugAnonStructures) {
                [resultString appendFormat:@"// %@\n", info.type.reallyBareTypeString];
                [resultString appendFormat:@"// depth: %lu, ref: %lu, used in method? %u\n", info.type.structureDepth, info.referenceCount, info.isUsedInMethod];
            }

            NSString *formattedString = [typeFormatter formatVariable:nil type:info.type];
            if (formattedString != nil) {
                //[resultString appendFormat:@"%@;\n\n", formattedString];
                [resultString appendFormat:@"typedef %@ %@;\n\n", formattedString, info.typedefName];
            }
        }
    }

    for (NSString *key in [[_phase3_namedStructureInfo allKeys] sortedArrayUsingSelector:@selector(compare:)]) {
        CDStructureInfo *info = _phase3_namedStructureInfo[key];
        BOOL shouldShow = info.type.isTemplateType && info.isUsedInMethod;
        if (shouldShow || debugAnonStructures) {
            if (hasAddedMark == NO) {
                [resultString appendFormat:@"#pragma mark %@\n\n", markName];
                hasAddedMark = YES;
            }

            if (hasShownExceptions == NO) {
                [resultString appendString:@"// Template types\n"];
                hasShownExceptions = YES;
            }

            if (debugAnonStructures) {
                [resultString appendFormat:@"// %@\n", info.type.reallyBareTypeString];
                [resultString appendFormat:@"// depth: %lu, ref: %lu, used in method? %u\n", info.type.structureDepth, info.referenceCount, info.isUsedInMethod];
            }

            NSString *formattedString = [typeFormatter formatVariable:nil type:info.type];
            if (formattedString != nil) {
                //[resultString appendFormat:@"%@;\n\n", formattedString];
                [resultString appendFormat:@"typedef %@ %@;\n\n", formattedString, info.typedefName];
            }
        }
    }
}

- (BOOL)shouldExpandStructureInfo:(CDStructureInfo *)info;
{
    return (info == nil)
        || (info.isUsedInMethod == NO
            && (info.type.isTemplateType == NO || info.isUsedInMethod == NO)
            && info.referenceCount < 2
            && (([info.name hasPrefix:@"_"] && [info.name hasUnderscoreCapitalPrefix] == NO) // TODO: Don't need the first hasPrefix check now.
                || [@"?" isEqualToString:info.name]));
}

// For automatic expansion?
- (BOOL)shouldExpandType:(CDType *)type;
{
    CDStructureInfo *info;
    NSString *name = [type.typeName description];
    if ([@"?" isEqualToString:name]) {
        NSString *key = type.reallyBareTypeString;
        info = _phase3_anonStructureInfo[key];
        if (info == nil) {
            // Look for an exception
            info = _phase3_anonExceptions[type.typeString];
        }
    } else {
        info = _phase3_namedStructureInfo[name];
        if (info == nil) {
            info = _phase3_nameExceptions[type.typeString];
            if (info != nil) {
                //NSLog(@"[%@] %s, found phase3 name exception... %@", identifier, __cmd, [info shortDescription]);
                //return NO;
            }
        }
    }

    return [self shouldExpandStructureInfo:info];
}

- (NSString *)typedefNameForType:(CDType *)type;
{
    CDStructureInfo *info = _phase3_anonStructureInfo[type.reallyBareTypeString];
    if (info == nil) {
        info = _phase3_anonExceptions[type.typeString];
        //NSLog(@"fallback typedef info? %@ -- %@", [info shortDescription], info.typedefName);
    }

    if (info == nil) {
        // Check name exceptions
        info = _phase3_nameExceptions[type.typeString];
#if 0
        if (info != nil)
            NSLog(@"Got typedef name for phase3 name exception: %@", info.typedefName);
#endif
    }

    if (info == nil) {
        info = _phase3_namedStructureInfo[[type.typeName description]];
    }
#if 0
    if (type.isTemplateType && info.typedefName == nil) {
        NSLog(@"Warning: no typedef name for type: %@", type.typeString);
    }
#endif

    return info.typedefName;
}

#pragma mark -

- (void)debugName:(NSString *)name;
{
    [_debugNames addObject:name];
}

- (void)debugAnon:(NSString *)str;
{
    [_debugAnon addObject:str];
}

- (void)logPhase0Info;
{
    NSLog(@"======================================================================");
    NSLog(@"[%@] %s", self.identifier, __cmd);
    for (CDStructureInfo *info in [[_phase0_structureInfo allValues] sortedArrayUsingSelector:@selector(ascendingCompareByStructureDepth:)]) {
        NSLog(@"%@", [info shortDescription]);
    }
    NSLog(@"======================================================================");
}

- (void)logPhase2Info;
{
#if 0
    NSLog(@"======================================================================");
    NSLog(@"[%@] %s, named:", identifier, __cmd);
    for (CDStructureInfo *info in [[phase2_namedStructureInfo allValues] sortedArrayUsingSelector:@selector(ascendingCompareByStructureDepth:)]) {
        NSLog(@"%@", [info shortDescription]);
    }
#endif
#if 0
    NSLog(@"======================================================================");
    NSLog(@"[%@] %s, anon:", identifier, __cmd);
    for (CDStructureInfo *info in [[phase2_anonStructureInfo allValues] sortedArrayUsingSelector:@selector(ascendingCompareByStructureDepth:)]) {
        NSLog(@"%@", [info shortDescription]);
    }
#endif
#if 1
    NSLog(@"======================================================================");
    NSLog(@"[%@] %s, named exceptions:", self.identifier, __cmd);
    for (CDStructureInfo *info in [_phase2_nameExceptions sortedArrayUsingSelector:@selector(ascendingCompareByStructureDepth:)]) {
        NSLog(@"%@", [info shortDescription]);
    }
#endif
#if 0
    NSLog(@"======================================================================");
    NSLog(@"[%@] %s, anon exceptions:", identifier, __cmd);
    for (CDStructureInfo *info in [phase2_anonExceptions sortedArrayUsingSelector:@selector(ascendingCompareByStructureDepth:)]) {
        NSLog(@"%@", [info shortDescription]);
    }
#endif
}

- (void)logPhase3Info;
{
    NSLog(@"[%@]  > %s", self.identifier, __cmd);
#if 0
    NSLog(@"----------------------------------------------------------------------");
    NSLog(@"named:");
    for (NSString *name in [[phase3_namedStructureInfo allKeys] sortedArrayUsingSelector:@selector(compare:)]) {
        CDStructureInfo *info = phase3_namedStructureInfo[name];
        NSLog(@"%@", [info shortDescription]);
    }
    
    NSLog(@"----------------------------------------------------------------------");
    NSLog(@"anon:");
    for (CDStructureInfo *info in [[phase3_anonStructureInfo allValues] sortedArrayUsingSelector:@selector(ascendingCompareByStructureDepth:)]) {
        NSLog(@"%@", [info shortDescription]);
    }
#endif
    NSLog(@"======================================================================");
    NSLog(@"[%@] %s, anon exceptions:", self.identifier, __cmd);
    for (CDStructureInfo *info in [[_phase3_anonExceptions allValues] sortedArrayUsingSelector:@selector(ascendingCompareByStructureDepth:)]) {
        NSLog(@"%@", [info shortDescription]);
    }
    
    NSLog(@"[%@] <  %s", self.identifier, __cmd);
}

@end
